package q2131_longestPalindrome;

import java.util.HashMap;
import java.util.Map;

public class Solution_2 {
    /*
    直接将所有的单词先记录到map中
    然后遍历map的keySet 如果其中有前后字符一致的单词 那么就考察其个数 以两两一对的方式加入到答案中 也就是 / 2 * 4的计算方式
    如果最后能够余下一个 那么就将add置2 最后加入答案（这个余下的即插入到回文字符串的中间）
    如果不是前后字符一致的 就直接考察单词与其反转单词的个数 取其中少的数 然后 * 2即可 （因为此后遍历到这个反转的单词还会加一次 所以不能够直接乘以4）
     */

    /*
    还可以直接用二维数组来替代hash表
    class Solution {
        int count[][]=new int[26][26];
        public int longestPalindrome(String[] words) {
            for(int i=0;i<words.length;i++){count[words[i].charAt(0)-'a'][words[i].charAt(1)-'a']++;}
            int add=0,ans=0;
            for(int i=0;i<26;i++){
                for(int j=i;j<26;j++){
                    if(i==j){
                        ans+=(count[i][i]>>1)<<2;
                        if((count[i][i]&1)==1){add=2;}
                    }
                    else{ans+=Math.min(count[i][j],count[j][i])<<2;}
                }
            }
            return ans+add;
        }
    }
     */
    public int longestPalindrome(String[] words) {
        Map<String,Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; ++i) map.put(words[i], map.getOrDefault(words[i],0) + 1);
        int add = 0, ans = 0;

        for (String s : map.keySet()) {
            if( s.charAt(0) == s.charAt(1) ) {
                ans += ((map.get(s) >> 1) << 2) ;
                if(((map.get(s) & 1) == 1)) add = 2;
            } else {
                String t = pal(s);
                if (map.containsKey(t)) ans += Math.min(map.get(s), map.get(t)) * 2;
            }
        }
        return ans + add;
    }
    public String pal(String s){
        return new StringBuilder(s).reverse().toString();
    }
}
